/**
 * 最小堆
 * 重要：索引从0开始时，节点i的父节点为(i - 1) / 2，左右子节点为i * 2 + 1和i * 2 + 2，最后一个非叶子节点为 (len - 2) / 2
 * 最后一个叶子节点为len - 1，其父节点就是最后一个非叶子节点 (len - 2) / 2
 */

#include <stddef.h>
#include "common.h"

typedef struct {
    void **data;
    size_t capacity;
    size_t len;
    cmp_t cmp;
} myheap;

#define HEAP_PARENT(i)        (i - 1) / 2
#define HEAP_LEFT_CHILD(i)    i * 2 + 1
#define HEAP_RIGHT_CHILD(i)   i * 2 + 2

myheap *heap_create(size_t c, cmp_t cmp);
myheap *heap_create_arr(void **arr, size_t len, size_t capacity, cmp_t cmp);
void heap_destory(myheap *h, int is_free_data);

// 维护以节点i为根的最小堆
void heapify(myheap *h, int i);
void heap_insert(myheap *h, void* data);
void *heap_remove(myheap *h);
void *heap_get(myheap *h);
int heap_empty(myheap *h);
int heap_full(myheap *h);
void heapify_all(myheap *h);
void heap_sort(void **arr, size_t len, cmp_t cmp);
void heap_set(myheap *h, int i, void *val);
